//给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 
//
// 有效 二叉搜索树定义如下： 
//
// 
// 节点的左子树只包含 小于 当前节点的数。 
// 节点的右子树只包含 大于 当前节点的数。 
// 所有左子树和右子树自身必须也是二叉搜索树。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [2,1,3]
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：root = [5,1,4,null,null,3,6]
//输出：false
//解释：根节点的值是 5 ，但是右子节点的值是 4 。
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数目范围在[1, 10⁴] 内 
// -2³¹ <= Node.val <= 2³¹ - 1 
// 
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 👍 1517 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class ValidateBinarySearchTree {
    public static void main(String[] args) {
        Solution solution = new ValidateBinarySearchTree().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        /**
         * 错误递归法（不能单独判断三个节点的值，需要判断所有左节点小于中节点，所有右节点大于中节点）
         *
         * @param root
         * @return
         */
//        public boolean isValidBST(TreeNode root) {
//            if (root.left == null && root.right == null) {
//                return true;
//            }
//
//            if (root.left != null) {
//                if (root.val > root.left.val) {
//                    isValidBST(root.left);
//                } else {
//                    return false;
//                }
//            }
//
//            if (root.right != null) {
//                if (root.val < root.right.val) {
//                    isValidBST(root.right);
//                } else {
//
//                    return false;
//                }
//            }
//
//            return true;
//        }

        /**
         * 解法一：中序遍历获得一个数组，判断数组是否升序
         *
         * @param root
         * @return
         */
//        List<Integer> res = new ArrayList<>();
//
//        public boolean isValidBST(TreeNode root) {
//            traversal(root);
//            // 对集合进行判断
//            for (int i = 1; i < res.size(); i++) {
//                if (res.get(i) <= res.get(i - 1)) {   // 二叉搜索树不能相等
//                    return false;
//                }
//            }
//            return true;
//        }
//
//        public TreeNode traversal(TreeNode root) {
//            if (root == null) {
//                return null;
//            }
//
//            if (root.left != null) traversal(root.left);
//            res.add(root.val);
//            if (root.right != null) traversal(root.right);
//
//            return root;
//        }

        /**
         * 递归法
         *
         * @param root
         * @return
         */
//        TreeNode pre = null;  // 用来记录前一个节点的值，注意需要设置为null，不能new，会默认将val设置为0，此时0的情况会判断为false
//
//        public boolean isValidBST(TreeNode root) {
//            if (root == null) { // 当为空时也为二叉搜索树
//                return true;
//            }
//
//            boolean left = isValidBST(root.left);// 左
//
//            if (pre != null && pre.val >= root.val) return false; // 右
//            pre = root; // 获取上一个节点
//
//            boolean right = isValidBST(root.right);// 右
//
//            return left && right;   // 判断左右是否为二叉搜索树
//        }
//    }

        /**
         * 迭代法（中序）
         *
         * @param root
         * @return
         */
        /*public boolean isValidBST(TreeNode root) {
            TreeNode pre = null;    // 用来记录前一个节点
            TreeNode cur = root;    // 用来记录前一个节点
            Stack<TreeNode> stack = new Stack<>();


            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left; // 一直将左孩子入栈
                } else {
                    cur = stack.pop();// 左孩子为空时
                    if (pre != null && pre.val >= cur.val) return false;
                    pre = cur;
                    cur = cur.right;
                }
            }

            return true;
        }*/

        // TreeNode pre = null;

        // 递归法
        /*public boolean isValidBST(TreeNode root) {
            // 空节点也是二叉搜索树
            if (root == null) return true;
            boolean left = isValidBST(root.left);

            if (pre != null && pre.val > root.val) return false;
            pre = root;

            boolean right = isValidBST(root.right);

            return left & right;
        }*/

        // 中序遍历迭代法
        /*public boolean isValidBST(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            TreeNode pre = null;

            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    cur = stack.pop();
                    if (pre != null && pre.val >= cur.val) return false;
                    pre = cur;
                    cur = cur.right;
                }
            }
            return true;
        }*/
        public boolean isValidBST(TreeNode root) {
            return traversal(root);
        }

        TreeNode pre;

        public boolean traversal(TreeNode root) {
            if (root == null) {
                return true;
            }

            if (!traversal(root.left)) return false;

            if (pre != null && pre.val > root.val) {
                return false;
            }
            pre = root;

            if (!traversal(root.right)) return false;

            return true;
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}
